package lecode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。
 * 请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
 *
 *提示：
 *
 * 1 <= intervals.length <= 104
 * intervals[i].length == 2
 * 0 <= starti <= endi <= 104
 *
 * 示例 1：
 *
 * 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
 * 输出：[[1,6],[8,10],[15,18]]
 * 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
 */
public class 合并区间56 {

    public static void main(String[] args) {
        int[][] nums = {{1,3},{8,10},{2,6},{15,18}};
        int[][] nums1 = merge(nums);
        System.out.println(Arrays.deepToString(nums1));
    }

    public static int[][] merge(int[][] intervals) {
        //对二维数组里面的数组排序
        Arrays.sort(intervals, (p, q) -> p[0] - q[0]);
        //返回结果集
        List<int[]> res = new ArrayList<>();
        //结果集与原数组值作比较
        for (int[] ints : intervals) {
            int m = res.size();
            //如果m=0 说明是第一个数组直接添加到res
            // origin: [[1,3],[2,6],[8,10],[15,18]]
            // res   : [[1,3]]
            //可以合并就合并，不可以合并的就添加
            //如果res的最后一组的最后一个元素小于原始数组的res下一组数据的第一个原始说明需要合并
            if (m > 0 && ints[0] <= res.get(m - 1)[1]) {
                res.get(m - 1)[1] = Math.max(res.get(m - 1)[1], ints[1]); // 更新右端点最大值
            } else {
                res.add(ints); // 新的合并区间
            }
        }
        return res.toArray(new int[res.size()][]);
    }

}
